/**
 *  递归 - 找出树最下面最左边的值 
 */
#include <iostream>
#include <queue>
#include <stack>
#include <vector>
using namespace std;

struct TreeNode {
    int val;
    TreeNode* left;
    TreeNode* right;
    TreeNode() : val(0), left(nullptr), right(nullptr){};
    TreeNode(int x) : val(x), left(nullptr), right(nullptr){};
    TreeNode(int x, TreeNode* left, TreeNode* right)
        : val(x), left(left), right(right){};
    void setVal(int x) { val = x; }
    void setAttribute(int x, TreeNode* l, TreeNode* r) {
        val = x;
        left = l;
        right = r;
    }
    void setChildren(TreeNode* l, TreeNode* r) {
        left = l;
        right = r;
    }
};

class Solution {
public:
    // 深度优先会在深度一样的情况下，第一个找到最左边的元素。
    void dfs(TreeNode *root, int height, int &curVal, int &curHeight) {
        if (root == nullptr) {
            return;
        }
        height++;
        dfs(root->left, height, curVal, curHeight);
        dfs(root->right, height, curVal, curHeight);
        if (height > curHeight) {
            curHeight = height;
            curVal = root->val;
        }
    }

    int findBottomLeftValue(TreeNode* root) {
        int curVal, curHeight = 0;
        dfs(root, 0, curVal, curHeight);
        return curVal;
    }
};

void test() {
    // 1. 构造一棵树。
    TreeNode* t1 = new TreeNode(1);
    TreeNode* t2 = new TreeNode(2);
    TreeNode* t3 = new TreeNode(3);
    TreeNode* t4 = new TreeNode(4);
    TreeNode* t5 = new TreeNode(5);
    TreeNode* t6 = new TreeNode(6);

    t1->setChildren(t2, t3);
    t2->setChildren(t4, t5);
    t5->setChildren(t6, nullptr);

    Solution s;
    cout << "二叉树最左最下面的树节点值为: " << s.findBottomLeftValue(t1) << endl;
}

int main() {
    test();
    return 0;
}